In the past computer systems typically executed sequences of instructions in a computer program in a strict sequential order. That is, instructions were executed in the actual order of the computer program.
Executing instructions in strict sequential order presented many limitations on the efficiency of executing instructions. For example, often the microprocessor would sit idle while waiting for the completion of a memory operation (e.g., a memory location being read or written). Meanwhile, subsequent instructions, which were not dependent on the memory operation being completed would nevertheless be required to wait to be executed, even though the microprocessor was not busy.
However, as computer systems and microprocessors have evolved, computer systems now are able to execute programs more efficiently. For example, the microprocessors execute instruction in a pipelined manner. In other words, multiple instructions can be executed simultaneously. That is, while one instruction is being executed, a subsequent instruction can be decoded, and another instruction can be fetched from a memory location.
In addition, advanced computer systems are able to perform multitasking (i.e., simultaneously execute two or more programs in one computer system.) More than one program can run simultaneously in the same computer because of the differences between I/O and processing speed. While one program is waiting for input, instructions in another can be executed. During the milliseconds one program waits for data to be read from a disk, millions of instructions in another program can be executed. For example, in interactive programs, thousands of instructions can be executed between each keystroke on the keyboard.
Moreover, advanced computer systems may also perform multitasking within a single program, commonly referred to as multithreading. That is, multi-threading allows multiple streams of execution to take place concurrently within the same program, each stream processing a different transaction or message.
One example of multi-threading could include the simultaneous execution of the different iterations of a loop in a pointer-based computer program. A loop consist of a set of instructions in a program that are executed repeatedly, either a fixed number of times or until some condition is true or false. Each pass through the set of instructions is referred to herein as an iteration.
The separate iterations of a loop will often operate on data stored in one or more fields in a particular record 101 of a pointer based data structure. Subsequent iterations will either execute data stored in the same record 101, or alternatively proceed to process one or more fields of another record 103, which may be connected to the previous record by a pointer 101e, as shown in pointer based data structure of FIG. 1.
As a result, in order to be able to concurrently execute the separate iterations of loop in the pointer based program, it typically should first be determined that the iterations of the loop are not dependent on each other. That is, if a first iteration writes to a particular memory location, and a second iteration reads the same memory location, then the second iteration can not be executed prior to the completion of the first iteration. Otherwise, the second iteration may read invalid data at the memory location to be updated by the first iteration. The determination of whether two or more iterations in a loop of a program operate on the same memory location, and thereby potentially prevent the concurrent execution of the iteration, is sometimes referred to as memory disambiguation.
If it is determined that separate iterations of a loop do not operate on the same memory locations, than the separate iterations are independent and can be scheduled to be executed simultaneously (a.k.a., loop_level parallelism), assuming the respective loop terminates. On the other hand, if separate iterations of a loop could possibly operate on the same memory location (e.g., the same fields within a record), then the iterations should not be simultaneously executed.
Therefore, a need exist for a method of determining whether separate iterations within a loop in a sequence of instructions in a pointer based application are independent because they do not operate on the same memory locations.